//Accepted
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <list>
#include <deque>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

long long x, y, n, j, sum;
int t;
int main (){
	//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
	scanf("%d", &t);
	while(t--){
	scanf("%d%d%d", &x, &y, &n);
	sum=1;
	for(j=1;j<=y;j<<=1,x=(x*x)%n){
		if(y&j){
			sum=(sum*x)%n;
		}
	}
	printf("%lld\n",sum);
	}
	
	return 0;
}
